package leetcode.todo;

/**
 * k个一组翻转链表
 *
 * ****   难难难   ***
 * TODO 解答失败 https://mp.weixin.qq.com/s/yOXeCjYWcZAI5A79ntXjaA
 */
public class Test25k个一组翻转链表 {

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode reverseKGroup(ListNode head, int k) {

        int tmp = k;
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        ListNode tmpHead = head;
        ListNode tmpTail = head; //临时尾巴指针
        ListNode head2 = null;
        while (true) {
            while (tmpTail != null && tmp != 1) {
                tmpTail = tmpTail.next;
                --tmp;
            }
            if (tmp != 1 || tmpTail == null) {
                break;
            }
            if(pre != null) {
                head2.next = tmpTail;
            }
            tmp = k;
            head = head == tmpHead ? tmpTail : head;
            cur = tmpHead;
            head2 = tmpHead;
            pre = tmpHead = tmpTail.next;
            while (cur != tmpHead) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            tmpTail = tmpHead;
        }

        return head;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;

        ListNode ans = reverseKGroup(l1, 3);
        while (ans != null) {
            System.out.print(ans.val);
            ans = ans.next;
        }
    }
}
